#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

vector<int> pathsWithMaxScore(vector<string>& board) {
    int n = board.size();
    const int mod = 1e9 + 7;
    vector<vector<int>> f(n + 1, vector<int>(n + 1));
    auto g = f;
    board[n - 1][n - 1] = '0';
    g[1][1] = 1;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            if (i + j == 0 || board[i][j] == 'X')    continue;
            int mx = 0;
            mx = max(mx, f[i + 1][j]);
            mx = max(mx, f[i][j + 1]);
            mx = max(mx, f[i][j]);
            f[i + 1][j + 1] = mx + board[i][j] - '0';
            if (mx > 0 || (i - 1 + j == 0) || (i + j - 1 == 0) || (i - 1 + j - 1 == 0))
            {
                if (mx == f[i + 1][j])
                    g[i + 1][j + 1] = (g[i + 1][j + 1] + g[i + 1][j]) % mod;
                if (mx == f[i][j + 1])
                    g[i + 1][j + 1] = (g[i + 1][j + 1] + g[i][j + 1]) % mod;
                if (mx == f[i][j])
                    g[i + 1][j + 1] = (g[i + 1][j + 1] + g[i][j]) % mod;
            }
        }

    return { g[n][n] > 0 ? f[n][n] : 0, g[n][n] };
}

int main()
{
    vector<string> vv = { "E23","2X2","12S" };
    pathsWithMaxScore(vv);
    return 0;
}